/// https://leetcode-cn.com/problems/combination-sum
pub struct Solution;

impl Solution {
    /// 前提：
    /// 1 <= candidates.length <= 30
    /// 1 <= candidates[i] <= 200
    /// 1 <= target <= 500
    /// candidate 中的每个元素都是独一无二的
    /// 和为 target 的唯一组合数少于 150 个
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = Vec::with_capacity(150);
        let mut v: Vec<i32> = Vec::with_capacity(150);
        // println!("\ncandidates: {:?} target: {}", candidates, target);
        Solution::backtrace(&candidates, 0, target, &mut res, &mut v);
        res
    }

    /// 产生的结果：大数字在前
    /// 如果小数字在前，比如
    /// vec![2, 3, 6, 7] target = 7 => vec![vec![2, 2, 3], vec![7]);
    /// 则参考：https://rustgym.com/leetcode/39
    /// 两种方式都能通过 leetcode ，而且 O ms 1.9 MB
    /// TODO: 回溯 + 剪枝 优化
    /// https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
    fn backtrace(candidates: &[i32], i: usize, target: i32, res: &mut Vec<Vec<i32>>,
                 v: &mut Vec<i32>) {
        // println!("target: {} i: {} v: {:?}", target, i, v);
        if i == candidates.len() {
            return;
        }
        if target == 0 {
            res.push(v.clone());
            return;
        }
        Solution::backtrace(candidates, i + 1, target, res, v);
        let d = candidates[i];
        if target >= d {
            v.push(d);
            // println!("push");
            Solution::backtrace(candidates, i, target - d, res, v);
            v.pop();
            // println!("pop");
        }
    }
}

/// 虽然数组比 vec 高效一些，但是涉及变长的情况，尽量还是利用一个 vec 来减少内存分配
/// 上面的方法可以内存只有 1.9 MB，而下面的方法需要 2.1 MB
impl Solution {
    pub fn combination_sum_slice(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = Vec::with_capacity(150);
        let mut v: [i32; 150] = [0; 150];
        // println!("\ncandidates: {:?} target: {}", candidates, target);
        Solution::backtrace_slice(&candidates, 0, 0, target, &mut res, &mut v);
        res
    }

    fn backtrace_slice(candidates: &[i32], i: usize, j: usize, target: i32,
                       res: &mut Vec<Vec<i32>>, v: &mut [i32]) {
        // println!("target: {} i: {} v: {:?}", target, i, &v[..5]);
        if i == candidates.len() {
            return;
        }
        if target == 0 {
            res.push(v.iter().take_while(|&&x| x > 0).map(|&x| x).collect()); // 每次都要分配内存
            return;
        }
        Solution::backtrace_slice(candidates, i + 1, j, target, res, v);
        if target >= candidates[i] {
            v[j] = candidates[i];
            // println!("push");
            Solution::backtrace_slice(candidates, i, j + 1, target - candidates[i], res, v);
            v[j] = 0;
            // println!("pop");
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert(f: impl Fn(Vec<i32>, i32) -> Vec<Vec<i32>>) {
        assert_eq!(f(vec![2, 3, 6, 7], 7), vec![vec![7], vec![2, 2, 3]]);
        // assert_eq!(f(vec![2, 3, 6, 7], 7), vec![vec![2, 2, 3], vec![7],]);
        assert_eq!(f(vec![2, 3, 5], 8), vec![vec![3, 5], vec![2, 3, 3], vec![2, 2, 2, 2]]);
        // assert_eq!(f(vec![2, 3, 5], 8), vec![vec![2, 2, 2, 2], vec![2, 3, 3], vec![3, 5]]);
        assert_eq!(f(vec![2,], 1), Vec::<Vec<i32>>::new());
        assert_eq!(f(vec![1,], 1), vec![vec![1]]);
        assert_eq!(f(vec![1,], 2), vec![vec![1, 1]]);
    }

    // combination_sum       : 1,265 ns/iter (+/- 132)
    // combination_sum_slice : 1,683 ns/iter (+/- 48)
    bench!(assert Solution::combination_sum);
    bench!(assert Solution::combination_sum_slice);
}
